﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace SortGUI
{
    public class MergeSort : SortBase
    {
        public override void Sort(int[] array)
        {
            Initialize();
            MergeSortAlgorithm(array, 0, array.Length - 1);
            Complete();
        }

        private void MergeSortAlgorithm(int[] array, int left, int right)
        {
            if (left < right)
            {
                int mid = (left + right) / 2;

                MergeSortAlgorithm(array, left, mid);
                MergeSortAlgorithm(array, mid + 1, right);
                Merge(array, left, mid, right);
            }
        }

        private void Merge(int[] array, int left, int mid, int right)
        {
            int n1 = mid - left + 1;
            int n2 = right - mid;
            int[] L = new int[n1];
            int[] R = new int[n2];
            Array.Copy(array, left, L, 0, n1);
            Array.Copy(array, mid + 1, R, 0, n2);
            int i = 0, j = 0, k = left;

            while (i < n1 && j < n2)
            {
                lastSwappedIndices[0] = left + i;
                lastSwappedIndices[1] = mid + 1 + j;
                if (L[i] <= R[j])
                {
                    array[k] = L[i];
                    i++;
                }
                else
                {
                    array[k] = R[j];
                    j++;
                }
                k++;
                count++;
                SortNextStep();

            }

            while (i < n1)
            {
                array[k] = L[i];
                i++;
                k++;
            }

            while (j < n2)
            {
                array[k] = R[j];
                j++;
                k++;
            }

        }

        public override void Initialize()
        {
            count = 0;
            updataColor(isInitialize = false);
        }

        public override void SortNextStep()
        {
            updateUiCallback(count, lastSwappedIndices, lastSortedIndex = 10000, swapped); // 更新UI
        }

        public override void Complete()
        {
            updateUiCallback(count, lastSwappedIndices, lastSortedIndex - 10000, swapped);
        }
    }
}